Lah number

In mathematics, Lah numbers, discovered by Ivo Lah in 1955,[1] are coefficients expressing rising factorials in terms of falling factorials.

Unsigned Lah numbers have an interesting meaning in combinatorics: they count the number of ways a set of n elements can be partitioned into k nonempty linearly ordered subsets. Lah numbers are related to Stirling numbers.

Unsigned Lah numbers:

L(n,k) = {n-1 \choose k-1} \frac{n!}{k!}.

Signed Lah numbers:

L'(n,k) = (-1)^n {n-1 \choose k-1} \frac{n!}{k!}.

L(n, 1) is always n!; using the interpretation above, the only partition of {1, 2, 3} into 1 set can be ordered in 6 ways:

{(1, 2, 3)}, {(1, 3, 2)}, {(2, 1, 3)}, {(2, 3, 1)}, {(3, 1, 2)} or {(3, 2, 1)}

L(3, 2) corresponds to the 6 partitions with two ordered parts:

{(1), (2, 3)}, {(1), (3, 2)}, {(2), (1, 3)}, {(2), (3, 1)}, {(3), (1, 2)} or {(3), (2, 1)}

L(n, n) is always 1: partitioning {1, 2, 3} into 3 non-empty subsets results in subsets of length 1.

{(1), (2), (3)}

Paraphrasing Karamata-Knuth notation for Stirling numbers, it was proposed to use the following alternative notation for Lah numbers:

L(n,k)=\left\lfloor\begin{matrix} n \\ k \end{matrix}\right\rfloor.

Contents

Rising and falling factorials

Let x^{(n)} represent the rising factorial x(x%2B1)(x%2B2) \cdots (x%2Bn-1) and let (x)_n represent the falling factorial x(x-1)(x-2) \cdots (x-n%2B1).

Then x^{(n)} = \sum_{k=1}^n L(n,k) (x)_k and (x)_n = \sum_{k=1}^n (-1)^{n-k} L(n,k)x^{(k)}.

For example, x(x%2B1)(x%2B2) = {\color{Red}6}x %2B {\color{Red}6}x(x-1) %2B {\color{Red}1}x(x-1)(x-2).

Compare the third row of the table of values.

Identities and relations

L(n,k) = {n-1 \choose k-1} \frac{n!}{k!} = {n \choose k} \frac{(n-1)!}{(k-1)!}
L(n,k) = \frac{n!(n-1)!}{k!(k-1)!}\cdot\frac{1}{(n-k)!} = \left (\frac{n!}{k!} \right )^2\frac{k}{n(n-k)!}
L(n,k%2B1) = \frac{n-k}{k(k%2B1)} L(n,k).
L(n,k) = \sum_{j} \left[{n\atop j}\right] \left\{{j\atop k}\right\}, with \left[{n\atop j}\right] the Stirling numbers of the first kind, \left\{{j\atop k}\right\} the Stirling numbers of the second kind and with the conventions L(0,0)=1 and L(n , k )=0 if k>n.
L(n,1) = n!
L(n,2) = (n-1)n!/2
L(n,3) = (n-2)(n-1)n!/12
L(n,n-1) = n(n-1)
L(n,n) = 1

Table of values

Below is a table of values for the Lah numbers:

_n\!\!\diagdown\!\!^k 1 2 3 4 5 6 7 8 9 10 11 12
1 1
2 2 1
3 6 6 1
4 24 36 12 1
5 120 240 120 20 1
6 720 1800 1200 300 30 1
7 5040 15120 12600 4200 630 42 1
8 40320 141120 141120 58800 11760 1176 56 1
9 362880 1451520 1693440 846720 211680 28224 2016 72 1
10 3628800 16329600 21772800 12700800 3810240 635040 60480 3240 90 1
11 39916800 199584000 299376000 199584000 69854400 13970880 1663200 11880 4950 110 1
12 479001600 2634508800 4390848000 3293136000 1317254400 307359360 43908480 3920400 217800 7260 132 1

See also

References

  1. ^ Introduction to Combinatorial Analysis Princeton University Press (1958, reissue 1980) ISBN 978-0691023656 (reprinted again in 2002, by Courier Dover Publications).